package com.booby.algorithm.quick;

import com.booby.algorithm.utils.Utils;

/**
 * 功能描述: 单轴快排，从大到小
 *
 * @author: lizt
 * @date: 2020/8/28 08:42
 **/

public class MaxToMIn {
    public static final Integer[] arr = {3,5,7,9,1,2,5,8,10};

    public static void sorted(Integer[] arr, int leftBound, int rightBound){
        if (leftBound >= rightBound){
            return;
        }
        int mid = partition(arr, leftBound, rightBound);
        sorted(arr, leftBound, mid -1);
        sorted(arr, mid + 1, rightBound);
    }

    /**
     * 功能描述:
     *
     * @param arr
     * @param leftBound  左边界集合索引值
     * @param rightBound 用边界结合索引值
     * @return: java.lang.Integer 左边界
     * @author: lizt
     * @date: 2020/8/28 09:08
    **/
    public static Integer partition(Integer[] arr, int leftBound, int rightBound){
        int pivot = arr[rightBound];
        int left = leftBound;
        int right = rightBound - 1;
        while (left <= right){
            while (left <= right && arr[left] >= pivot){
                left++;
            }
            while (left <= right && arr[right] < pivot){
                right--;
            }
            if (left < right){
                Utils.swap(arr, left, right);
            }
        }
        // 交换轴
        Utils.swap(arr, left, rightBound);

        return left;
    }

    public static void main(String[] args) {
        sorted(arr, 0, arr.length - 1);
        Utils.print(arr);
    }
}
